package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author tzp
 * @since 2020/9/15
 */
public class LC120 implements DynamicProblem {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;
        if (triangle.size() == 1) return triangle.get(0).get(0);

        int[][] state = new int[triangle.size()][triangle.size()];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            List<Integer> thisLevel = triangle.get(i);
            if (i == triangle.size() - 1) {//最下层
                for (int j = 0; j < thisLevel.size(); j++) {
                    state[i][j] = thisLevel.get(j);
                }
            } else {
                for (int j = 0; j < thisLevel.size(); j++) {
                    state[i][j] = thisLevel.get(j) + Math.min(state[i + 1][j], state[i + 1][j + 1]);
                }
                //合着是我想多了, 还想横着走
//                int[] tmp = new int[thisLevel.size()];
//                for (int j = 0; j < thisLevel.size(); j++) {
//                    int min = state[i][j];//bugfix
//                    if (j > 0) {
//                        min = Math.min(state[i][j], thisLevel.get(j) + state[i][j - 1]);
//                    }
//                    if (j < thisLevel.size() - 1) {
//                        min = Math.min(state[i][j], thisLevel.get(j) + state[i][j + 1]);
//                    }
//                    tmp[j] = min;
//                }
//                state[i] = tmp;
            }
        }
        return state[0][0];
    }

    public static void main(String[] args) {
//        Integer[][] a = new Integer[][]{
//                {2},
//                {3, 4},
//                {6, 5, 7},
//                {4, 1, 8, 3}
//        };

//        Integer[][] a = new Integer[][]{
//                    {2},
//                   {3, 0},
//                  {0, 0, 7},
//                {0, 1, 8, 3}
//        };
        // @formatter:off
        Integer[][] a = new Integer[][]{
                     {1},
                   {-2, -5},
                  {3,  6,  9},
                {-1, 2,  4, -3}
        };
        // @formatter:on
        List<List<Integer>> list = Arrays.stream(a)
                .map(Arrays::asList)
                .collect(Collectors.toList());

        System.out.println(new LC120().minimumTotal(list));
    }
}
